
package fillpolygon;


import java.util.ArrayList;
import processing.core.*;

public class FillPolygon extends PApplet {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        PApplet.main(new String[]{"fillpolygon.FillPolygon"});
    }

    private ArrayList ordenar(ArrayList line, Node nodo) {
        boolean index = false;
        if (line.isEmpty()) {
            line.add(nodo);
        } else {
            for (int i = 0; i < line.size(); i++) {
                if (((Node) line.get(i)).xMin >= nodo.xMin) {
                    if (((Node) line.get(i)).xMin == nodo.xMin) {
                        if (((Node) line.get(i)).mInverse >= nodo.mInverse) {
                            index = true;
                            line.add(i, nodo);
                            break;
                        }
                    } else {
                        index = true;
                        line.add(i, nodo);
                        break;
                    }

                }
            }
            if (index == false) {
                line.add(nodo);
            }
        }
        return line;
    }

    private void fillPolygon() {
        boolean par = false;
        ArrayList scanline;
        activeEdgeTable.set(0, edgeTable.get(0));
        for (int i = 1; i < activeEdgeTable.size(); i++) {
            //Se iguala con las posibles aristas que intersecan la scanline
            activeEdgeTable.set(i, edgeTable.get(i));
            scanline = (ArrayList) activeEdgeTable.get(i - 1);
            if (scanline.isEmpty() == false) {
                //Se borran las aristas que no intersecan
                for (int j = 0; j < scanline.size(); j++) {
                    if (((Node) scanline.get(j)).yMax == i-1) {
                        scanline.remove(j);
                        j--;
                    }
                }


//                for (int j = 0; j < scanline.size(); j++) {
//                        scanline.set(j, new Node(((Node) scanline.get(j)).yMax, (float) (((Node) scanline.get(j)).xMin + (float) ((Node) scanline.get(j)).mInverse), ((Node) scanline.get(j)).mInverse));
//                }

                //Se ordena
                for (int j = 0; j < scanline.size(); j++) {
                    activeEdgeTable.set(i, ordenar(((ArrayList) activeEdgeTable.get(i)), (Node) scanline.get(j)));
                }
                //se calculan los valores de x
                
                                for (int j = 0; j < scanline.size(); j++) {
                        ((ArrayList) activeEdgeTable.get(i)).set(j, new Node(((Node) ((ArrayList) activeEdgeTable.get(i)).get(j)).yMax, (float) (((Node) ((ArrayList) activeEdgeTable.get(i)).get(j)).xMin + (float) ((Node) ((ArrayList) activeEdgeTable.get(i)).get(j)).mInverse), ((Node) ((ArrayList) activeEdgeTable.get(i)).get(j)).mInverse));
                }


            }
        }

        //Se dibuja (por fin xD)
        background(255);
        for (int i = 0; i < activeEdgeTable.size(); i++) {
            par = false;
            stroke(0,255,0);
            noFill();
            beginShape(LINES);
            if (((ArrayList) activeEdgeTable.get(i)).isEmpty() == false) {
                scanline = (ArrayList) activeEdgeTable.get(i);
                for (int j = 0; j < scanline.size(); j++) {
                if(par==false){
                    vertex(round(((Node) scanline.get(j)).xMin), i);
                par=true;
                }
                else{
                vertex(round(((Node) scanline.get(j)).xMin), i);
                    par=false;
                }
                    
                }
            }
            endShape();
        }
        
    }

    class Node {

        Node(PVector a, PVector b) {
            mInverse = (a.x - b.x) / (a.y - b.y);
            if(mInverse>0){
            if (a.y > b.y) {
                yMax = a.y;
                if (a.x < b.x) {
                    xMin = a.x;
                } else {
                    xMin = b.x;
                }
            } else if (a.y < b.y) {
                yMax = b.y;
                if (a.x < b.x) {
                    xMin = a.x;
                } else {
                    xMin = b.x;
                }
            }
            }
            else
            {
            if (a.y > b.y) {
                yMax = a.y;
                if (a.x < b.x) {
                    xMin = b.x;
                } else {
                    xMin = a.x;
                }
            } else if (a.y < b.y) {
                yMax = b.y;
                if (a.x < b.x) {
                    xMin = b.x;
                } else {
                    xMin = a.x;
                }
            }
            }
        }

        Node(float a, float b, float c) {
            yMax = a;
            xMin = b;
            mInverse = c;
        }
        public float yMax;
        public float xMin;
        public float mInverse;
    }
    ArrayList puntos = new ArrayList();
    ArrayList edgeTable = new ArrayList();
    ArrayList activeEdgeTable = new ArrayList();

    @Override
    public void setup() {
        size(800, 600);

    }

    @Override
    public void draw() {
        stroke(0);
        noFill();
        beginShape();
        for (int i = 0; i < puntos.size(); i++) {
            vertex(((PVector) puntos.get(i)).x, ((PVector) puntos.get(i)).y);
        }
        endShape();
        stroke(255);
    }

    @Override
    public void mouseClicked() {
        if(mouseButton == LEFT) {
            if(puntos.isEmpty()){
            puntos.add(new PVector(mouseX, mouseY));
     puntos.add(new PVector(mouseX, mouseY));
            }
            else{
    puntos.add(puntos.size()-1,new PVector(mouseX, mouseY));
        }
  } else {
    puntos.clear();
    puntos.add(new PVector(mouseX, mouseY));
     puntos.add(new PVector(mouseX, mouseY));
  }
        buildET();
        fillPolygon();
    }
    
    

    void buildET() {
        inicializarTabla();
        PVector puntoActual, puntoSiguiente;
        for (int i = 0; i < puntos.size() - 1; i++) {
            puntoActual = ((PVector) puntos.get(i));
            puntoSiguiente = ((PVector) puntos.get(i + 1));
            if (puntoActual.y < puntoSiguiente.y) {

                edgeTable.set(round(puntoActual.y), ordenar((ArrayList) edgeTable.get(round(puntoActual.y)), new Node(puntoActual, puntoSiguiente)));
            } else if (puntoActual.y > puntoSiguiente.y) {

                edgeTable.set(round(puntoSiguiente.y), ordenar((ArrayList) edgeTable.get(round(puntoSiguiente.y)), new Node(puntoActual, puntoSiguiente)));
            }


        }



    }

    private void inicializarTabla() {
        edgeTable.clear();
        for (int i = 0; i < this.height; i++) {
            edgeTable.add(new ArrayList());
        }
        activeEdgeTable.clear();
        for (int i = 0; i < this.height; i++) {
            activeEdgeTable.add(new ArrayList());
        }
    }
}
